#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title028.py 
@version:
@time: 2023/05/14
HJ28.素数伴侣

若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。
现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，
挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，
而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，
当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:

输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。

输入
4
2 5 6 13

输出
2
"""
import math


def check(num):  # 判断是否是素数
    for i in range(2, int(math.sqrt(num)) + 2):
        if (num % i == 0):
            return False
    return True


def find(odd, visited, choose, evens):  # 配对的过程
    for j, even in enumerate(evens):
        if check(odd + even) and not visited[j]:
            visited[j] = True  # 代表这两个数能配对
            if choose[j] == 0 or find(choose[j], visited, choose, evens):
                choose[j] = odd  # 当前奇数已经和当前的偶数配对
                return True
    return False


while True:
    try:
        num = int(input())
        a: str = input()
        a: list = a.split()
        b = []
        count = 0
        for i in range(len(a)):
            a[i] = int(a[i])
        evens = []
        odds = []
        for i in a:  # 将输入的数分为奇数和偶数
            if (i % 2 == 0):
                odds.append(i)
            else:
                evens.append(i)
        choose = [0] * len(evens)  # choose用来存放当前和这个奇数配对的那个偶数
        for odd in odds:
            visited = [False] * len(evens)  # visit用来存放当前奇数和偶数是否已经配过对
            if find(odd, visited, choose, evens):
                count += 1
        print(count)
    except:
        break
